package com.my.java.algorithm.sort;

import java.util.Arrays;

public class QuickSort {
        static int count = 0;

        public static void main(String[] args) {
                int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51 };
                quick(a);
                for (int i = 0; i < a.length; i++)
                        System.out.println(a[i]);
        }

        public static int getMiddle(int[] list, int low, int high) {
                int tmp = list[low]; // 数组的第一个作为中轴
                while (low < high) {
                        //1. 高位指针与基数比较
                        while (low < high && list[high] >= tmp) {
                                high--;
                        }
                        list[low] = list[high]; // 比中轴小的记录移到低端
                        
                        
                        //2. 低位指针与基数比较
                        while (low < high && list[low] <= tmp) {
                                low++;
                        }
                        list[high] = list[low]; // 比中轴大的记录移到高端
                }
                //3. 基数归位
                list[low] = tmp; // 中轴记录到尾
                return low; // 返回中轴的位置
        }

        public static  void quickSort(int[] list, int low, int high) {
                System.out.println(Arrays.toString(list));
                if (low < high) {
                        int middle = getMiddle(list, low, high); // 将list数组进行一分为二
                        quickSort(list, low, middle - 1); // 对低字表进行递归排序
                        quickSort(list, middle + 1, high); // 对高字表进行递归排序
                }
        }
        
        private static String printArr(int[] list){
                StringBuffer sb = new StringBuffer();
                for(int i=0;i<list.length;i++){
                        sb.append(list[i]).append(",");
                }
                sb.append("\n");
                return sb.toString();
        }

        public static void quick(int[] a2) {
                if (a2.length > 0) { // 查看数组是否为空
                        quickSort(a2, 0, a2.length - 1);
                }
        }
}